package com.learn.algorithm.dynamic.programming;

public class Leet1143Code {

    public static int longestCommonSubsequence(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n = s1.length;
        int m = s2.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int len1 = 1; len1 < n + 1; len1++) {
            for (int len2 = 1; len2 < m + 1; len2++) {
                if (s1[len1 - 1] == s2[len2 - 1]) {
                    dp[len1][len2] = 1 + dp[len1 - 1][len2 - 1];
                } else {
                    dp[len1][len2] = Math.max(dp[len1][len2 - 1], dp[len1 - 1][len2]);
                }
            }
        }
        return dp[n][m];
    }

    public static int longestCommonSubsequence3(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n = s1.length;
        int m = s2.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = -1;
            }
        }
        return f3(s1, s2, n, m, dp);
    }

    // 记忆化搜索版本
    public static int f3(char[] s1, char[] s2, int len1, int len2, int[][] dp) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        if (dp[len1][len2] != -1) {
            return dp[len1][len2];
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f3(s1, s2, len1 - 1, len2 - 1, dp) + 1;
        } else {
            ans = Math.max(f3(s1, s2, len1 - 1, len2, dp), f3(s1, s2, len1, len2 - 1, dp));
        }
        dp[len1][len2] = ans;
        return ans;
    }

    public static int longestCommonSubsequence2(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n = s1.length;
        int m = s2.length;
        return f2(s1, s2, n, m);
    }

    // 为了避免多边界讨论
    // 很多时候不使用下标定义尝试 而是使用长度定义尝试
    // 因为长度最短是0, 而下标越界讨论起来比较麻烦
    // s1[前缀长度len1] 对应 s2[前缀长度len2]
    // len1 = 6 代表 s1[0..5]
    public static int f2(char[] s1, char[] s2, int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        int ans;
        if (s1[len1 - 1] == s2[len2 - 1]) {
            ans = f2(s1, s2, len1 - 1, len2 - 1) + 1;
        } else {
            ans = Math.max(f2(s1, s2, len1 - 1, len2), f2(s1, s2, len1, len2 - 1));
        }
        return ans;
    }


    public static int longestCommonSubsequence1(String text1, String text2) {
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int n = s1.length;
        int m = s2.length;
        return f1(s1, s2, n - 1, m - 1);
    }

    // s1[..., i1] 和 s2[..., i2]的最长公共子序列
    public static int f1(char[] s1, char[] s2, int i1, int i2) {
        if (i1 < 0 || i2 < 0) {
            return 0;
        }
        int p1 = f1(s1, s2, i1 - 1, i2 - 1);
        int p2 = f1(s1, s2, i1 - 1, i2);
        int p3 = f1(s1, s2, i1, i2 - 1);
        int p4 = s1[i1] == s2[i2] ? (1 + p1) : 0;
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace"));
        System.out.println(longestCommonSubsequence("abc", "abc"));
        System.out.println(longestCommonSubsequence("abc", "def"));
    }
}
